/*
 * Copyright (C) 2007 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.dx.cf.code;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;

import com.android.dx.rop.code.AccessFlags;
import com.android.dx.rop.code.BasicBlock;
import com.android.dx.rop.code.BasicBlockList;
import com.android.dx.rop.code.Insn;
import com.android.dx.rop.code.InsnList;
import com.android.dx.rop.code.PlainCstInsn;
import com.android.dx.rop.code.PlainInsn;
import com.android.dx.rop.code.RegisterSpec;
import com.android.dx.rop.code.RegisterSpecList;
import com.android.dx.rop.code.Rop;
import com.android.dx.rop.code.RopMethod;
import com.android.dx.rop.code.Rops;
import com.android.dx.rop.code.SourcePosition;
import com.android.dx.rop.code.ThrowingCstInsn;
import com.android.dx.rop.code.ThrowingInsn;
import com.android.dx.rop.code.TranslationAdvice;
import com.android.dx.rop.cst.CstInteger;
import com.android.dx.rop.cst.CstType;
import com.android.dx.rop.type.Prototype;
import com.android.dx.rop.type.StdTypeList;
import com.android.dx.rop.type.Type;
import com.android.dx.rop.type.TypeList;
import com.android.dx.util.Bits;
import com.android.dx.util.Hex;
import com.android.dx.util.IntList;

/**
 * Utility that converts a basic block list into a list of register-oriented
 * blocks.
 */
public final class Ropper {

	/** label offset for the parameter assignment block */
	private static final int PARAM_ASSIGNMENT = -1;

	/** label offset for the return block */
	private static final int RETURN = -2;

	/** label offset for the synchronized method final return block */
	private static final int SYNCH_RETURN = -3;

	/** label offset for the first synchronized method setup block */
	private static final int SYNCH_SETUP_1 = -4;

	/** label offset for the second synchronized method setup block */
	private static final int SYNCH_SETUP_2 = -5;

	/**
	 * label offset for the first synchronized method exception handler block
	 */
	private static final int SYNCH_CATCH_1 = -6;

	/**
	 * label offset for the second synchronized method exception handler block
	 */
	private static final int SYNCH_CATCH_2 = -7;

	/** number of special label offsets */
	private static final int SPECIAL_LABEL_COUNT = 7;

	/** {@code non-null;} method being converted */
	private final ConcreteMethod method;

	/** {@code non-null;} original block list */
	private final ByteBlockList blocks;

	/** max locals of the method */
	private final int maxLocals;

	/** max label (exclusive) of any original bytecode block */
	private final int maxLabel;

	/** {@code non-null;} simulation machine to use */
	private final RopperMachine machine;

	/** {@code non-null;} simulator to use */
	private final Simulator sim;

	/**
	 * {@code non-null;} sparse array mapping block labels to initial frame
	 * contents, if known
	 */
	private final Frame[] startFrames;

	/** {@code non-null;} output block list in-progress */
	private final ArrayList<BasicBlock> result;

	/**
	 * {@code non-null;} list of subroutine-nest labels (See
	 * {@link Frame#getSubroutines} associated with each result block. Parallel
	 * to {@link Ropper#result}.
	 */
	private final ArrayList<IntList> resultSubroutines;

	/**
	 * {@code non-null;} for each block (by label) that is used as an exception
	 * handler, the type of exception it catches
	 */
	private final Type[] catchTypes;

	/**
	 * whether an exception-handler block for a synchronized method was ever
	 * required
	 */
	private boolean synchNeedsExceptionHandler;

	/**
	 * {@code non-null;} list of subroutines indexed by label of start address
	 */
	private final Subroutine[] subroutines;

	/** true if {@code subroutines} is non-empty */
	private boolean hasSubroutines;

	/**
	 * Keeps track of subroutines that exist in java form and are inlined in Rop
	 * form.
	 */
	private class Subroutine {

		/** list of all blocks that jsr to this subroutine */
		private BitSet callerBlocks;
		/** List of all blocks that return from this subroutine */
		private BitSet retBlocks;
		/** first block in this subroutine */
		private int startBlock;

		/**
		 * Constructs instance.
		 * 
		 * @param startBlock
		 *            First block of the subroutine.
		 */
		Subroutine(int startBlock) {
			this.startBlock = startBlock;
			retBlocks = new BitSet(maxLabel);
			callerBlocks = new BitSet(maxLabel);
			hasSubroutines = true;
		}

		/**
		 * Constructs instance.
		 * 
		 * @param startBlock
		 *            First block of the subroutine.
		 * @param retBlock
		 *            one of the ret blocks (final blocks) of this subroutine.
		 */
		Subroutine(int startBlock, int retBlock) {
			this(startBlock);
			addRetBlock(retBlock);
		}

		/**
		 * @return {@code >= 0;} the label of the subroutine's start block.
		 */
		int getStartBlock() {
			return startBlock;
		}

		/**
		 * Adds a label to the list of ret blocks (final blocks) for this
		 * subroutine.
		 * 
		 * @param retBlock
		 *            ret block label
		 */
		void addRetBlock(int retBlock) {
			retBlocks.set(retBlock);
		}

		/**
		 * Adds a label to the list of caller blocks for this subroutine.
		 * 
		 * @param label
		 *            a block that invokes this subroutine.
		 */
		void addCallerBlock(int label) {
			callerBlocks.set(label);
		}

		/**
		 * Generates a list of subroutine successors. Note: successor blocks
		 * could be listed more than once. This is ok, because this successor
		 * list (and the block it's associated with) will be copied and inlined
		 * before we leave the ropper. Redundent successors will result in
		 * redundent (no-op) merges.
		 * 
		 * @return all currently known successors (return destinations) for that
		 *         subroutine
		 */
		IntList getSuccessors() {
			IntList successors = new IntList(callerBlocks.size());

			/*
			 * For each subroutine caller, get it's target. If the target is us,
			 * add the ret target (subroutine successor) to our list
			 */

			for (int label = callerBlocks.nextSetBit(0); label >= 0; label = callerBlocks
					.nextSetBit(label + 1)) {
				BasicBlock subCaller = labelToBlock(label);
				successors.add(subCaller.getSuccessors().get(0));
			}

			successors.setImmutable();

			return successors;
		}

		/**
		 * Merges the specified frame into this subroutine's successors, setting
		 * {@code workSet} as appropriate. To be called with the frame of a
		 * subroutine ret block.
		 * 
		 * @param frame
		 *            {@code non-null;} frame from ret block to merge
		 * @param workSet
		 *            {@code non-null;} workset to update
		 */
		void mergeToSuccessors(Frame frame, int[] workSet) {
			for (int label = callerBlocks.nextSetBit(0); label >= 0; label = callerBlocks
					.nextSetBit(label + 1)) {
				BasicBlock subCaller = labelToBlock(label);
				int succLabel = subCaller.getSuccessors().get(0);

				Frame subFrame = frame.subFrameForLabel(startBlock, label);

				if (subFrame != null) {
					mergeAndWorkAsNecessary(succLabel, -1, null, subFrame,
							workSet);
				} else {
					Bits.set(workSet, label);
				}
			}
		}
	}

	/**
	 * Converts a {@link ConcreteMethod} to a {@link RopMethod}.
	 * 
	 * @param method
	 *            {@code non-null;} method to convert
	 * @param advice
	 *            {@code non-null;} translation advice to use
	 * @return {@code non-null;} the converted instance
	 */
	public static RopMethod convert(ConcreteMethod method,
			TranslationAdvice advice) {
		try {
			Ropper r = new Ropper(method, advice);
			r.doit();
			return r.getRopMethod();
		} catch (SimException ex) {
			ex.addContext("...while working on method "
					+ method.getNat().toHuman());
			throw ex;
		}
	}

	/**
	 * Constructs an instance. This class is not publicly instantiable; use
	 * {@link #convert}.
	 * 
	 * @param method
	 *            {@code non-null;} method to convert
	 * @param advice
	 *            {@code non-null;} translation advice to use
	 */
	private Ropper(ConcreteMethod method, TranslationAdvice advice) {
		if (method == null) {
			throw new NullPointerException("method == null");
		}

		if (advice == null) {
			throw new NullPointerException("advice == null");
		}

		this.method = method;
		this.blocks = BasicBlocker.identifyBlocks(method);
		this.maxLabel = blocks.getMaxLabel();
		this.maxLocals = method.getMaxLocals();
		this.machine = new RopperMachine(this, method, advice);
		this.sim = new Simulator(machine, method);
		this.startFrames = new Frame[maxLabel];
		this.subroutines = new Subroutine[maxLabel];

		/*
		 * The "* 2 + 10" below is to conservatively believe that every block is
		 * an exception handler target and should also take care of enough other
		 * possible extra overhead such that the underlying array is unlikely to
		 * need resizing.
		 */
		this.result = new ArrayList<BasicBlock>(blocks.size() * 2 + 10);
		this.resultSubroutines = new ArrayList<IntList>(blocks.size() * 2 + 10);

		this.catchTypes = new Type[maxLabel];
		this.synchNeedsExceptionHandler = false;

		/*
		 * Set up the first stack frame with the right limits, but leave it
		 * empty here (to be filled in outside of the constructor).
		 */
		startFrames[0] = new Frame(maxLocals, method.getMaxStack());
	}

	/**
	 * Gets the first (lowest) register number to use as the temporary area when
	 * unwinding stack manipulation ops.
	 * 
	 * @return {@code >= 0;} the first register to use
	 */
	/* package */int getFirstTempStackReg() {
		/*
		 * We use the register that is just past the deepest possible stack
		 * element, plus one if the method is synchronized to avoid overlapping
		 * with the synch register. We don't need to do anything else special at
		 * this level, since later passes will merely notice the highest
		 * register used by explicit inspection.
		 */
		int regCount = getNormalRegCount();
		return isSynchronized() ? regCount + 1 : regCount;
	}

	/**
	 * Gets the label for the exception handler setup block corresponding to the
	 * given label.
	 * 
	 * @param label
	 *            {@code >= 0;} the original label
	 * @return {@code >= 0;} the corresponding exception handler setup label
	 */
	private int getExceptionSetupLabel(int label) {
		return maxLabel + label;
	}

	/**
	 * Gets the label for the given special-purpose block. The given label
	 * should be one of the static constants defined by this class.
	 * 
	 * @param label
	 *            {@code < 0;} the special label constant
	 * @return {@code >= 0;} the actual label value to use
	 */
	private int getSpecialLabel(int label) {
		/*
		 * The label is bitwise-complemented so that mistakes where LABEL is
		 * used instead of getSpecialLabel(LABEL) cause a failure at block
		 * construction time, since negative labels are illegal. We multiply
		 * maxLabel by 2 since 0..maxLabel (exclusive) are the original blocks
		 * and maxLabel..(maxLabel*2) are reserved for exception handler setup
		 * blocks (see getExceptionSetupLabel(), above).
		 */
		return (maxLabel * 2) + ~label;
	}

	/**
	 * Gets the minimum label for unreserved use.
	 * 
	 * @return {@code >= 0;} the minimum label
	 */
	private int getMinimumUnreservedLabel() {
		/*
		 * The labels below ((maxLabel * 2) + SPECIAL_LABEL_COUNT) are reserved
		 * for particular uses.
		 */

		return (maxLabel * 2) + SPECIAL_LABEL_COUNT;
	}

	/**
	 * Gets an arbitrary unreserved and available label.
	 * 
	 * @return {@code >= 0;} the label
	 */
	private int getAvailableLabel() {
		int candidate = getMinimumUnreservedLabel();

		for (BasicBlock bb : result) {
			int label = bb.getLabel();
			if (label >= candidate) {
				candidate = label + 1;
			}
		}

		return candidate;
	}

	/**
	 * Gets whether the method being translated is synchronized.
	 * 
	 * @return whether the method being translated is synchronized
	 */
	private boolean isSynchronized() {
		int accessFlags = method.getAccessFlags();
		return (accessFlags & AccessFlags.ACC_SYNCHRONIZED) != 0;
	}

	/**
	 * Gets whether the method being translated is static.
	 * 
	 * @return whether the method being translated is static
	 */
	private boolean isStatic() {
		int accessFlags = method.getAccessFlags();
		return (accessFlags & AccessFlags.ACC_STATIC) != 0;
	}

	/**
	 * Gets the total number of registers used for "normal" purposes (i.e., for
	 * the straightforward translation from the original Java).
	 * 
	 * @return {@code >= 0;} the total number of registers used
	 */
	private int getNormalRegCount() {
		return maxLocals + method.getMaxStack();
	}

	/**
	 * Gets the register spec to use to hold the object to synchronize on, for a
	 * synchronized method.
	 * 
	 * @return {@code non-null;} the register spec
	 */
	private RegisterSpec getSynchReg() {
		/*
		 * We use the register that is just past the deepest possible stack
		 * element, with a minimum of v1 since v0 is what's always used to hold
		 * the caught exception when unwinding. We don't need to do anything
		 * else special at this level, since later passes will merely notice the
		 * highest register used by explicit inspection.
		 */
		int reg = getNormalRegCount();
		return RegisterSpec.make((reg < 1) ? 1 : reg, Type.OBJECT);
	}

	/**
	 * Searches {@link #result} for a block with the given label. Returns its
	 * index if found, or returns {@code -1} if there is no such block.
	 * 
	 * @param label
	 *            the label to look for
	 * @return {@code >= -1;} the index for the block with the given label or
	 *         {@code -1} if there is no such block
	 */
	private int labelToResultIndex(int label) {
		int sz = result.size();
		for (int i = 0; i < sz; i++) {
			BasicBlock one = result.get(i);
			if (one.getLabel() == label) {
				return i;
			}
		}

		return -1;
	}

	/**
	 * Searches {@link #result} for a block with the given label. Returns it if
	 * found, or throws an exception if there is no such block.
	 * 
	 * @param label
	 *            the label to look for
	 * @return {@code non-null;} the block with the given label
	 */
	private BasicBlock labelToBlock(int label) {
		int idx = labelToResultIndex(label);

		if (idx < 0) {
			throw new IllegalArgumentException("no such label " + Hex.u2(label));
		}

		return result.get(idx);
	}

	/**
	 * Adds a block to the output result.
	 * 
	 * @param block
	 *            {@code non-null;} the block to add
	 * @param subroutines
	 *            {@code non-null;} subroutine label list as described in
	 *            {@link Frame#getSubroutines}
	 */
	private void addBlock(BasicBlock block, IntList subroutines) {
		if (block == null) {
			throw new NullPointerException("block == null");
		}

		result.add(block);
		subroutines.throwIfMutable();
		resultSubroutines.add(subroutines);
	}

	/**
	 * Adds or replace a block in the output result. If this is a replacement,
	 * then any extra blocks that got added with the original get removed as a
	 * result of calling this method.
	 * 
	 * @param block
	 *            {@code non-null;} the block to add or replace
	 * @param subroutines
	 *            {@code non-null;} subroutine label list as described in
	 *            {@link Frame#getSubroutines}
	 * @return {@code true} if the block was replaced or {@code false} if it was
	 *         added for the first time
	 */
	private boolean addOrReplaceBlock(BasicBlock block, IntList subroutines) {
		if (block == null) {
			throw new NullPointerException("block == null");
		}

		int idx = labelToResultIndex(block.getLabel());
		boolean ret;

		if (idx < 0) {
			ret = false;
		} else {
			/*
			 * We are replacing a pre-existing block, so find any blocks that
			 * got added as part of the original and remove those too. Such
			 * blocks are (possibly indirect) successors of this block which are
			 * out of the range of normally-translated blocks.
			 */
			removeBlockAndSpecialSuccessors(idx);
			ret = true;
		}

		result.add(block);
		subroutines.throwIfMutable();
		resultSubroutines.add(subroutines);
		return ret;
	}

	/**
	 * Adds or replaces a block in the output result. Do not delete any
	 * successors.
	 * 
	 * @param block
	 *            {@code non-null;} the block to add or replace
	 * @param subroutines
	 *            {@code non-null;} subroutine label list as described in
	 *            {@link Frame#getSubroutines}
	 * @return {@code true} if the block was replaced or {@code false} if it was
	 *         added for the first time
	 */
	private boolean addOrReplaceBlockNoDelete(BasicBlock block,
			IntList subroutines) {
		if (block == null) {
			throw new NullPointerException("block == null");
		}

		int idx = labelToResultIndex(block.getLabel());
		boolean ret;

		if (idx < 0) {
			ret = false;
		} else {
			result.remove(idx);
			resultSubroutines.remove(idx);
			ret = true;
		}

		result.add(block);
		subroutines.throwIfMutable();
		resultSubroutines.add(subroutines);
		return ret;
	}

	/**
	 * Helper for {@link #addOrReplaceBlock} which recursively removes the given
	 * block and all blocks that are (direct and indirect) successors of it
	 * whose labels indicate that they are not in the normally-translated range.
	 * 
	 * @param idx
	 *            {@code non-null;} block to remove (etc.)
	 */
	private void removeBlockAndSpecialSuccessors(int idx) {
		int minLabel = getMinimumUnreservedLabel();
		BasicBlock block = result.get(idx);
		IntList successors = block.getSuccessors();
		int sz = successors.size();

		result.remove(idx);
		resultSubroutines.remove(idx);

		for (int i = 0; i < sz; i++) {
			int label = successors.get(i);
			if (label >= minLabel) {
				idx = labelToResultIndex(label);
				if (idx < 0) {
					throw new RuntimeException("Invalid label " + Hex.u2(label));
				}
				removeBlockAndSpecialSuccessors(idx);
			}
		}
	}

	/**
	 * Extracts the resulting {@link RopMethod} from the instance.
	 * 
	 * @return {@code non-null;} the method object
	 */
	private RopMethod getRopMethod() {

		// Construct the final list of blocks.

		int sz = result.size();
		BasicBlockList bbl = new BasicBlockList(sz);
		for (int i = 0; i < sz; i++) {
			bbl.set(i, result.get(i));
		}
		bbl.setImmutable();

		// Construct the method object to wrap it all up.

		/*
		 * Note: The parameter assignment block is always the first that should
		 * be executed, hence the second argument to the constructor.
		 */
		return new RopMethod(bbl, getSpecialLabel(PARAM_ASSIGNMENT));
	}

	/**
	 * Does the conversion.
	 */
	private void doit() {
		int[] workSet = Bits.makeBitSet(maxLabel);

		Bits.set(workSet, 0);
		addSetupBlocks();
		setFirstFrame();

		for (;;) {
			int offset = Bits.findFirst(workSet, 0);
			if (offset < 0) {
				break;
			}
			Bits.clear(workSet, offset);
			ByteBlock block = blocks.labelToBlock(offset);
			Frame frame = startFrames[offset];
			try {
				processBlock(block, frame, workSet);
			} catch (SimException ex) {
				ex.addContext("...while working on block " + Hex.u2(offset));
				throw ex;
			}
		}

		addReturnBlock();
		addSynchExceptionHandlerBlock();
		addExceptionSetupBlocks();

		if (hasSubroutines) {
			// Subroutines are very rare, so skip this step if it's n/a
			inlineSubroutines();
		}
	}

	/**
	 * Sets up the first frame to contain all the incoming parameters in locals.
	 */
	private void setFirstFrame() {
		Prototype desc = method.getEffectiveDescriptor();
		startFrames[0].initializeWithParameters(desc.getParameterTypes());
		startFrames[0].setImmutable();
	}

	/**
	 * Processes the given block.
	 * 
	 * @param block
	 *            {@code non-null;} block to process
	 * @param frame
	 *            {@code non-null;} start frame for the block
	 * @param workSet
	 *            {@code non-null;} bits representing work to do, which this
	 *            method may add to
	 */
	private void processBlock(ByteBlock block, Frame frame, int[] workSet) {
		// Prepare the list of caught exceptions for this block.
		ByteCatchList catches = block.getCatches();
		machine.startBlock(catches.toRopCatchList());

		/*
		 * Using a copy of the given frame, simulate each instruction, calling
		 * into machine for each.
		 */
		frame = frame.copy();
		sim.simulate(block, frame);
		frame.setImmutable();

		int extraBlockCount = machine.getExtraBlockCount();
		ArrayList<Insn> insns = machine.getInsns();
		int insnSz = insns.size();

		/*
		 * Merge the frame into each possible non-exceptional successor.
		 */

		int catchSz = catches.size();
		IntList successors = block.getSuccessors();

		int startSuccessorIndex;

		Subroutine calledSubroutine = null;
		if (machine.hasJsr()) {
			/*
			 * If this frame ends in a JSR, only merge our frame with the
			 * subroutine start, not the subroutine's return target.
			 */
			startSuccessorIndex = 1;

			int subroutineLabel = successors.get(1);

			if (subroutines[subroutineLabel] == null) {
				subroutines[subroutineLabel] = new Subroutine(subroutineLabel);
			}

			subroutines[subroutineLabel].addCallerBlock(block.getLabel());

			calledSubroutine = subroutines[subroutineLabel];
		} else if (machine.hasRet()) {
			/*
			 * This block ends in a ret, which means it's the final block in
			 * some subroutine. Ultimately, this block will be copied and
			 * inlined for each call and then disposed of.
			 */

			ReturnAddress ra = machine.getReturnAddress();
			int subroutineLabel = ra.getSubroutineAddress();

			if (subroutines[subroutineLabel] == null) {
				subroutines[subroutineLabel] = new Subroutine(subroutineLabel,
						block.getLabel());
			} else {
				subroutines[subroutineLabel].addRetBlock(block.getLabel());
			}

			successors = subroutines[subroutineLabel].getSuccessors();
			subroutines[subroutineLabel].mergeToSuccessors(frame, workSet);
			// Skip processing below since we just did it.
			startSuccessorIndex = successors.size();
		} else if (machine.wereCatchesUsed()) {
			/*
			 * If there are catches, then the first successors (which will
			 * either be all of them or all but the last one) are catch targets.
			 */
			startSuccessorIndex = catchSz;
		} else {
			startSuccessorIndex = 0;
		}

		int succSz = successors.size();
		for (int i = startSuccessorIndex; i < succSz; i++) {
			int succ = successors.get(i);
			try {
				mergeAndWorkAsNecessary(succ, block.getLabel(),
						calledSubroutine, frame, workSet);
			} catch (SimException ex) {
				ex.addContext("...while merging to block " + Hex.u2(succ));
				throw ex;
			}
		}

		if ((succSz == 0) && machine.returns()) {
			/*
			 * The block originally contained a return, but it has been made to
			 * instead end with a goto, and we need to tell it at this point
			 * that its sole successor is the return block. This has to happen
			 * after the merge loop above, since, at this point, the return
			 * block doesn't actually exist; it gets synthesized at the end of
			 * processing the original blocks.
			 */
			successors = IntList.makeImmutable(getSpecialLabel(RETURN));
			succSz = 1;
		}

		int primarySucc;

		if (succSz == 0) {
			primarySucc = -1;
		} else {
			primarySucc = machine.getPrimarySuccessorIndex();
			if (primarySucc >= 0) {
				primarySucc = successors.get(primarySucc);
			}
		}

		/*
		 * This variable is true only when the method is synchronized and the
		 * block being processed can possibly throw an exception.
		 */
		boolean synch = isSynchronized() && machine.canThrow();

		if (synch || (catchSz != 0)) {
			/*
			 * Deal with exception handlers: Merge an exception-catch frame into
			 * each possible exception handler, and construct a new set of
			 * successors to point at the exception handler setup blocks (which
			 * get synthesized at the very end of processing).
			 */
			boolean catchesAny = false;
			IntList newSucc = new IntList(succSz);
			for (int i = 0; i < catchSz; i++) {
				ByteCatchList.Item one = catches.get(i);
				CstType exceptionClass = one.getExceptionClass();
				int targ = one.getHandlerPc();

				catchesAny |= (exceptionClass == CstType.OBJECT);

				Frame f = frame.makeExceptionHandlerStartFrame(exceptionClass);

				try {
					mergeAndWorkAsNecessary(targ, block.getLabel(), null, f,
							workSet);
				} catch (SimException ex) {
					ex.addContext("...while merging exception to block "
							+ Hex.u2(targ));
					throw ex;
				}

				/*
				 * Set up the exception handler type, by setting it if the given
				 * handler has yet to be encountered, or by conservatively
				 * unioning if it has.
				 */
				Type already = catchTypes[targ];
				if (already == null) {
					catchTypes[targ] = exceptionClass.getClassType();
				} else if (already != exceptionClass.getClassType()) {
					catchTypes[targ] = Type.OBJECT;
				}

				/*
				 * The synthesized exception setup block will have the label
				 * getExceptionSetupLabel(targ).
				 */
				newSucc.add(getExceptionSetupLabel(targ));
			}

			if (synch && !catchesAny) {
				/*
				 * The method is synchronized and this block doesn't already
				 * have a catch-all handler, so add one to the end, both in the
				 * successors and in the throwing instruction(s) at the end of
				 * the block (which is where the caught classes live).
				 */
				newSucc.add(getSpecialLabel(SYNCH_CATCH_1));
				synchNeedsExceptionHandler = true;

				for (int i = insnSz - extraBlockCount - 1; i < insnSz; i++) {
					Insn insn = insns.get(i);
					if (insn.canThrow()) {
						insn = insn.withAddedCatch(Type.OBJECT);
						insns.set(i, insn);
					}
				}
			}

			if (primarySucc >= 0) {
				newSucc.add(primarySucc);
			}

			newSucc.setImmutable();
			successors = newSucc;
		}

		// Construct the final resulting block(s), and store it (them).

		int primarySuccListIndex = successors.indexOf(primarySucc);

		/*
		 * If there are any extra blocks, work backwards through the list of
		 * instructions, adding single-instruction blocks, and resetting the
		 * successors variables as appropriate.
		 */
		for (/* extraBlockCount */; extraBlockCount > 0; extraBlockCount--) {
			/*
			 * Some of the blocks that the RopperMachine wants added are for
			 * move-result insns, and these need goto insns as well.
			 */
			Insn extraInsn = insns.get(--insnSz);
			boolean needsGoto = extraInsn.getOpcode().getBranchingness() == Rop.BRANCH_NONE;
			InsnList il = new InsnList(needsGoto ? 2 : 1);
			IntList extraBlockSuccessors = successors;

			il.set(0, extraInsn);

			if (needsGoto) {
				il.set(1, new PlainInsn(Rops.GOTO, extraInsn.getPosition(),
						null, RegisterSpecList.EMPTY));
				/*
				 * Obviously, this block won't be throwing an exception so it
				 * should only have one successor.
				 */
				extraBlockSuccessors = IntList.makeImmutable(primarySucc);
			}
			il.setImmutable();

			int label = getAvailableLabel();
			BasicBlock bb = new BasicBlock(label, il, extraBlockSuccessors,
					primarySucc);
			// All of these extra blocks will be in the same subroutine
			addBlock(bb, frame.getSubroutines());

			successors = successors.mutableCopy();
			successors.set(primarySuccListIndex, label);
			successors.setImmutable();
			primarySucc = label;
		}

		Insn lastInsn = (insnSz == 0) ? null : insns.get(insnSz - 1);

		/*
		 * Add a goto to the end of the block if it doesn't already end with a
		 * branch, to maintain the invariant that all blocks end with a branch
		 * of some sort or other. Note that it is possible for there to be
		 * blocks for which no instructions were ever output (e.g., only consist
		 * of pop* in the original Java bytecode).
		 */
		if ((lastInsn == null)
				|| (lastInsn.getOpcode().getBranchingness() == Rop.BRANCH_NONE)) {
			SourcePosition pos = (lastInsn == null) ? SourcePosition.NO_INFO
					: lastInsn.getPosition();
			insns.add(new PlainInsn(Rops.GOTO, pos, null,
					RegisterSpecList.EMPTY));
			insnSz++;
		}

		/*
		 * Construct a block for the remaining instructions (which in the usual
		 * case is all of them).
		 */

		InsnList il = new InsnList(insnSz);
		for (int i = 0; i < insnSz; i++) {
			il.set(i, insns.get(i));
		}
		il.setImmutable();

		BasicBlock bb = new BasicBlock(block.getLabel(), il, successors,
				primarySucc);
		addOrReplaceBlock(bb, frame.getSubroutines());
	}

	/**
	 * Helper for {@link #processBlock}, which merges frames and adds to the
	 * work set, as necessary.
	 * 
	 * @param label
	 *            {@code >= 0;} label to work on
	 * @param pred
	 *            predecessor label; must be {@code >= 0} when {@code label} is
	 *            a subroutine start block and calledSubroutine is non-null.
	 *            Otherwise, may be -1.
	 * @param calledSubroutine
	 *            {@code null-ok;} a Subroutine instance if {@code label} is the
	 *            first block in a subroutine.
	 * @param frame
	 *            {@code non-null;} new frame for the labelled block
	 * @param workSet
	 *            {@code non-null;} bits representing work to do, which this
	 *            method may add to
	 */
	private void mergeAndWorkAsNecessary(int label, int pred,
			Subroutine calledSubroutine, Frame frame, int[] workSet) {
		Frame existing = startFrames[label];
		Frame merged;

		if (existing != null) {
			/*
			 * Some other block also continues at this label. Merge the frames,
			 * and re-set the bit in the work set if there was a change.
			 */
			if (calledSubroutine != null) {
				merged = existing.mergeWithSubroutineCaller(frame,
						calledSubroutine.getStartBlock(), pred);
			} else {
				merged = existing.mergeWith(frame);
			}
			if (merged != existing) {
				startFrames[label] = merged;
				Bits.set(workSet, label);
			}
		} else {
			// This is the first time this label has been encountered.
			if (calledSubroutine != null) {
				startFrames[label] = frame.makeNewSubroutineStartFrame(label,
						pred);
			} else {
				startFrames[label] = frame;
			}
			Bits.set(workSet, label);
		}
	}

	/**
	 * Constructs and adds the blocks that perform setup for the rest of the
	 * method. This includes a first block which merely contains assignments
	 * from parameters to the same-numbered registers and a possible second
	 * block which deals with synchronization.
	 */
	private void addSetupBlocks() {
		LocalVariableList localVariables = method.getLocalVariables();
		SourcePosition pos = method.makeSourcePosistion(0);
		Prototype desc = method.getEffectiveDescriptor();
		StdTypeList params = desc.getParameterTypes();
		int sz = params.size();
		InsnList insns = new InsnList(sz + 1);
		int at = 0;

		for (int i = 0; i < sz; i++) {
			Type one = params.get(i);
			LocalVariableList.Item local = localVariables.pcAndIndexToLocal(0,
					at);
			RegisterSpec result = (local == null) ? RegisterSpec.make(at, one)
					: RegisterSpec.makeLocalOptional(at, one,
							local.getLocalItem());

			Insn insn = new PlainCstInsn(Rops.opMoveParam(one), pos, result,
					RegisterSpecList.EMPTY, CstInteger.make(at));
			insns.set(i, insn);
			at += one.getCategory();
		}

		insns.set(sz, new PlainInsn(Rops.GOTO, pos, null,
				RegisterSpecList.EMPTY));
		insns.setImmutable();

		boolean synch = isSynchronized();
		int label = synch ? getSpecialLabel(SYNCH_SETUP_1) : 0;
		BasicBlock bb = new BasicBlock(getSpecialLabel(PARAM_ASSIGNMENT),
				insns, IntList.makeImmutable(label), label);
		addBlock(bb, IntList.EMPTY);

		if (synch) {
			RegisterSpec synchReg = getSynchReg();
			Insn insn;
			if (isStatic()) {
				insn = new ThrowingCstInsn(Rops.CONST_OBJECT, pos,
						RegisterSpecList.EMPTY, StdTypeList.EMPTY,
						method.getDefiningClass());
				insns = new InsnList(1);
				insns.set(0, insn);
			} else {
				insns = new InsnList(2);
				insn = new PlainCstInsn(Rops.MOVE_PARAM_OBJECT, pos, synchReg,
						RegisterSpecList.EMPTY, CstInteger.VALUE_0);
				insns.set(0, insn);
				insns.set(1, new PlainInsn(Rops.GOTO, pos, null,
						RegisterSpecList.EMPTY));
			}

			int label2 = getSpecialLabel(SYNCH_SETUP_2);
			insns.setImmutable();
			bb = new BasicBlock(label, insns, IntList.makeImmutable(label2),
					label2);
			addBlock(bb, IntList.EMPTY);

			insns = new InsnList(isStatic() ? 2 : 1);

			if (isStatic()) {
				insns.set(0, new PlainInsn(Rops.opMoveResultPseudo(synchReg),
						pos, synchReg, RegisterSpecList.EMPTY));
			}

			insn = new ThrowingInsn(Rops.MONITOR_ENTER, pos,
					RegisterSpecList.make(synchReg), StdTypeList.EMPTY);
			insns.set(isStatic() ? 1 : 0, insn);
			insns.setImmutable();
			bb = new BasicBlock(label2, insns, IntList.makeImmutable(0), 0);
			addBlock(bb, IntList.EMPTY);
		}
	}

	/**
	 * Constructs and adds the return block, if necessary. The return block
	 * merely contains an appropriate {@code return} instruction.
	 */
	private void addReturnBlock() {
		Rop returnOp = machine.getReturnOp();

		if (returnOp == null) {
			/*
			 * The method being converted never returns normally, so there's no
			 * need for a return block.
			 */
			return;
		}

		SourcePosition returnPos = machine.getReturnPosition();
		int label = getSpecialLabel(RETURN);

		if (isSynchronized()) {
			InsnList insns = new InsnList(1);
			Insn insn = new ThrowingInsn(Rops.MONITOR_EXIT, returnPos,
					RegisterSpecList.make(getSynchReg()), StdTypeList.EMPTY);
			insns.set(0, insn);
			insns.setImmutable();

			int nextLabel = getSpecialLabel(SYNCH_RETURN);
			BasicBlock bb = new BasicBlock(label, insns,
					IntList.makeImmutable(nextLabel), nextLabel);
			addBlock(bb, IntList.EMPTY);

			label = nextLabel;
		}

		InsnList insns = new InsnList(1);
		TypeList sourceTypes = returnOp.getSources();
		RegisterSpecList sources;

		if (sourceTypes.size() == 0) {
			sources = RegisterSpecList.EMPTY;
		} else {
			RegisterSpec source = RegisterSpec.make(0, sourceTypes.getType(0));
			sources = RegisterSpecList.make(source);
		}

		Insn insn = new PlainInsn(returnOp, returnPos, null, sources);
		insns.set(0, insn);
		insns.setImmutable();

		BasicBlock bb = new BasicBlock(label, insns, IntList.EMPTY, -1);
		addBlock(bb, IntList.EMPTY);
	}

	/**
	 * Constructs and adds, if necessary, the catch-all exception handler block
	 * to deal with unwinding the lock taken on entry to a synchronized method.
	 */
	private void addSynchExceptionHandlerBlock() {
		if (!synchNeedsExceptionHandler) {
			/*
			 * The method being converted either isn't synchronized or can't
			 * possibly throw exceptions in its main body, so there's no need
			 * for a synchronized method exception handler.
			 */
			return;
		}

		SourcePosition pos = method.makeSourcePosistion(0);
		RegisterSpec exReg = RegisterSpec.make(0, Type.THROWABLE);
		BasicBlock bb;
		Insn insn;

		InsnList insns = new InsnList(2);
		insn = new PlainInsn(Rops.opMoveException(Type.THROWABLE), pos, exReg,
				RegisterSpecList.EMPTY);
		insns.set(0, insn);
		insn = new ThrowingInsn(Rops.MONITOR_EXIT, pos,
				RegisterSpecList.make(getSynchReg()), StdTypeList.EMPTY);
		insns.set(1, insn);
		insns.setImmutable();

		int label2 = getSpecialLabel(SYNCH_CATCH_2);
		bb = new BasicBlock(getSpecialLabel(SYNCH_CATCH_1), insns,
				IntList.makeImmutable(label2), label2);
		addBlock(bb, IntList.EMPTY);

		insns = new InsnList(1);
		insn = new ThrowingInsn(Rops.THROW, pos, RegisterSpecList.make(exReg),
				StdTypeList.EMPTY);
		insns.set(0, insn);
		insns.setImmutable();

		bb = new BasicBlock(label2, insns, IntList.EMPTY, -1);
		addBlock(bb, IntList.EMPTY);
	}

	/**
	 * Creates the exception handler setup blocks. "maxLocals" below is because
	 * that's the register number corresponding to the sole element on a
	 * one-deep stack (which is the situation at the start of an exception
	 * handler block).
	 */
	private void addExceptionSetupBlocks() {

		int len = catchTypes.length;
		for (int i = 0; i < len; i++) {
			Type one = catchTypes[i];
			if (one != null) {
				Insn proto = labelToBlock(i).getFirstInsn();
				SourcePosition pos = proto.getPosition();
				InsnList il = new InsnList(2);

				Insn insn = new PlainInsn(Rops.opMoveException(one), pos,
						RegisterSpec.make(maxLocals, one),
						RegisterSpecList.EMPTY);
				il.set(0, insn);

				insn = new PlainInsn(Rops.GOTO, pos, null,
						RegisterSpecList.EMPTY);
				il.set(1, insn);
				il.setImmutable();

				BasicBlock bb = new BasicBlock(getExceptionSetupLabel(i), il,
						IntList.makeImmutable(i), i);
				addBlock(bb, startFrames[i].getSubroutines());
			}
		}
	}

	/**
	 * Checks to see if the basic block is a subroutine caller block.
	 * 
	 * @param bb
	 *            {@code non-null;} the basic block in question
	 * @return true if this block calls a subroutine
	 */
	private boolean isSubroutineCaller(BasicBlock bb) {
		IntList successors = bb.getSuccessors();
		if (successors.size() < 2)
			return false;

		int subLabel = successors.get(1);

		return (subLabel < subroutines.length)
				&& (subroutines[subLabel] != null);
	}

	/**
	 * Inlines any subroutine calls.
	 */
	private void inlineSubroutines() {
		final IntList reachableSubroutineCallerLabels = new IntList(4);

		/*
		 * Compile a list of all subroutine calls reachable through the normal
		 * (non-subroutine) flow. We do this first, since we'll be affecting the
		 * call flow as we go.
		 * 
		 * Start at label 0 -- the param assignment block has nothing for us
		 */
		forEachNonSubBlockDepthFirst(0, new BasicBlock.Visitor() {

			public void visitBlock(BasicBlock b) {
				if (isSubroutineCaller(b)) {
					reachableSubroutineCallerLabels.add(b.getLabel());
				}
			}
		});

		/*
		 * Convert the resultSubroutines list, indexed by block index, to a
		 * label-to-subroutines mapping used by the inliner.
		 */
		int largestAllocedLabel = getAvailableLabel();
		ArrayList<IntList> labelToSubroutines = new ArrayList<IntList>(
				largestAllocedLabel);
		for (int i = 0; i < largestAllocedLabel; i++) {
			labelToSubroutines.add(null);
		}

		for (int i = 0; i < result.size(); i++) {
			BasicBlock b = result.get(i);
			if (b == null) {
				continue;
			}
			IntList subroutineList = resultSubroutines.get(i);
			labelToSubroutines.set(b.getLabel(), subroutineList);
		}

		/*
		 * Inline all reachable subroutines. Inner subroutines will be inlined
		 * as they are encountered.
		 */
		int sz = reachableSubroutineCallerLabels.size();
		for (int i = 0; i < sz; i++) {
			int label = reachableSubroutineCallerLabels.get(i);
			new SubroutineInliner(new LabelAllocator(getAvailableLabel()),
					labelToSubroutines)
					.inlineSubroutineCalledFrom(labelToBlock(label));
		}

		// Now find the blocks that aren't reachable and remove them
		deleteUnreachableBlocks();
	}

	/**
	 * Deletes all blocks that cannot be reached. This is run to delete original
	 * subroutine blocks after subroutine inlining.
	 */
	private void deleteUnreachableBlocks() {
		final IntList reachableLabels = new IntList(result.size());

		// subroutine inlining is done now and we won't update this list here
		resultSubroutines.clear();

		forEachNonSubBlockDepthFirst(getSpecialLabel(PARAM_ASSIGNMENT),
				new BasicBlock.Visitor() {

					public void visitBlock(BasicBlock b) {
						reachableLabels.add(b.getLabel());
					}
				});

		reachableLabels.sort();

		for (int i = result.size() - 1; i >= 0; i--) {
			if (reachableLabels.indexOf(result.get(i).getLabel()) < 0) {
				result.remove(i);
				// unnecessary here really, since subroutine inlining is done
				// resultSubroutines.remove(i);
			}
		}
	}

	/**
	 * Allocates labels, without requiring previously allocated labels to have
	 * been added to the blocks list.
	 */
	private static class LabelAllocator {

		int nextAvailableLabel;

		/**
		 * @param startLabel
		 *            available label to start allocating from
		 */
		LabelAllocator(int startLabel) {
			nextAvailableLabel = startLabel;
		}

		/**
		 * @return next available label
		 */
		int getNextLabel() {
			return nextAvailableLabel++;
		}
	}

	/**
	 * Inlines a subroutine. Start by calling
	 * {@link #inlineSubroutineCalledFrom}.
	 */
	private class SubroutineInliner {

		/**
		 * maps original label to the label that will be used by the inlined
		 * version
		 */
		private final HashMap<Integer, Integer> origLabelToCopiedLabel;

		/** set of original labels that need to be copied */
		private final BitSet workList;

		/** the label of the original start block for this subroutine */
		private int subroutineStart;

		/** the label of the ultimate return block */
		private int subroutineSuccessor;

		/** used for generating new labels for copied blocks */
		private final LabelAllocator labelAllocator;

		/**
		 * A mapping, indexed by label, to subroutine nesting list. The
		 * subroutine nest list is as returned by {@link Frame#getSubroutines}.
		 */
		private final ArrayList<IntList> labelToSubroutines;

		SubroutineInliner(final LabelAllocator labelAllocator,
				ArrayList<IntList> labelToSubroutines) {
			origLabelToCopiedLabel = new HashMap<Integer, Integer>();

			workList = new BitSet(maxLabel);

			this.labelAllocator = labelAllocator;
			this.labelToSubroutines = labelToSubroutines;
		}

		/**
		 * Inlines a subroutine.
		 * 
		 * @param b
		 *            block where {@code jsr} occurred in the original bytecode
		 */
		void inlineSubroutineCalledFrom(final BasicBlock b) {
			/*
			 * The 0th successor of a subroutine caller block is where the
			 * subroutine should return to. The 1st successor is the start block
			 * of the subroutine.
			 */
			subroutineSuccessor = b.getSuccessors().get(0);
			subroutineStart = b.getSuccessors().get(1);

			/*
			 * This allocates an initial label and adds the first block to the
			 * worklist.
			 */
			int newSubStartLabel = mapOrAllocateLabel(subroutineStart);

			for (int label = workList.nextSetBit(0); label >= 0; label = workList
					.nextSetBit(0)) {
				workList.clear(label);
				int newLabel = origLabelToCopiedLabel.get(label);

				copyBlock(label, newLabel);

				if (isSubroutineCaller(labelToBlock(label))) {
					new SubroutineInliner(labelAllocator, labelToSubroutines)
							.inlineSubroutineCalledFrom(labelToBlock(newLabel));
				}
			}

			/*
			 * Replace the original caller block, since we now have a new
			 * successor
			 */

			addOrReplaceBlockNoDelete(new BasicBlock(b.getLabel(),
					b.getInsns(), IntList.makeImmutable(newSubStartLabel),
					newSubStartLabel), labelToSubroutines.get(b.getLabel()));
		}

		/**
		 * Copies a basic block, mapping its successors along the way.
		 * 
		 * @param origLabel
		 *            original block label
		 * @param newLabel
		 *            label that the new block should have
		 */
		private void copyBlock(int origLabel, int newLabel) {

			BasicBlock origBlock = labelToBlock(origLabel);

			final IntList origSuccessors = origBlock.getSuccessors();
			IntList successors;
			int primarySuccessor = -1;
			Subroutine subroutine;

			if (isSubroutineCaller(origBlock)) {
				/*
				 * A subroutine call inside a subroutine call. Set up so we can
				 * recurse. The caller block should have it's first successor be
				 * a copied block that will be the subroutine's return point.
				 * It's second successor will be copied when we recurse, and
				 * remains as the original label of the start of the inner
				 * subroutine.
				 */

				successors = IntList.makeImmutable(
						mapOrAllocateLabel(origSuccessors.get(0)),
						origSuccessors.get(1));
				// primary successor will be set when this block is replaced
			} else if (null != (subroutine = subroutineFromRetBlock(origLabel))) {
				/*
				 * this is a ret block -- its successor should be
				 * subroutineSuccessor
				 */

				// Sanity check
				if (subroutine.startBlock != subroutineStart) {
					throw new RuntimeException(
							"ret instruction returns to label "
									+ Hex.u2(subroutine.startBlock)
									+ " expected: " + Hex.u2(subroutineStart));
				}

				successors = IntList.makeImmutable(subroutineSuccessor);
				primarySuccessor = subroutineSuccessor;
			} else {
				// Map all the successor labels

				int origPrimary = origBlock.getPrimarySuccessor();
				int sz = origSuccessors.size();

				successors = new IntList(sz);

				for (int i = 0; i < sz; i++) {
					int origSuccLabel = origSuccessors.get(i);
					int newSuccLabel = mapOrAllocateLabel(origSuccLabel);

					successors.add(newSuccLabel);

					if (origPrimary == origSuccLabel) {
						primarySuccessor = newSuccLabel;
					}
				}

				successors.setImmutable();
			}

			addBlock(new BasicBlock(newLabel,
					filterMoveReturnAddressInsns(origBlock.getInsns()),
					successors, primarySuccessor),
					labelToSubroutines.get(newLabel));
		}

		/**
		 * Checks to see if a specified label is involved in a specified
		 * subroutine.
		 * 
		 * @param label
		 *            {@code >= 0;} a basic block label
		 * @param subroutineStart
		 *            {@code >= 0;} a subroutine as identified by the label of
		 *            its start block
		 * @return true if the block is dominated by the subroutine call
		 */
		private boolean involvedInSubroutine(int label, int subroutineStart) {
			IntList subroutinesList = labelToSubroutines.get(label);
			return (subroutinesList != null && subroutinesList.size() > 0 && subroutinesList
					.top() == subroutineStart);
		}

		/**
		 * Maps the label of a pre-copied block to the label of the inlined
		 * block, allocating a new label and adding it to the worklist if
		 * necessary. If the origLabel is a "special" label, it is returned
		 * exactly and not scheduled for duplication: copying never proceeds
		 * past a special label, which likely is the function return block or an
		 * immediate predecessor.
		 * 
		 * @param origLabel
		 *            label of original, pre-copied block
		 * @return label for new, inlined block
		 */
		private int mapOrAllocateLabel(int origLabel) {
			int resultLabel;
			Integer mappedLabel = origLabelToCopiedLabel.get(origLabel);

			if (mappedLabel != null) {
				resultLabel = mappedLabel;
			} else if (!involvedInSubroutine(origLabel, subroutineStart)) {
				/*
				 * A subroutine has ended by some means other than a "ret"
				 * (which really means a throw caught later).
				 */
				resultLabel = origLabel;
			} else {
				resultLabel = labelAllocator.getNextLabel();
				workList.set(origLabel);
				origLabelToCopiedLabel.put(origLabel, resultLabel);

				// The new label has the same frame as the original label
				while (labelToSubroutines.size() <= resultLabel) {
					labelToSubroutines.add(null);
				}
				labelToSubroutines.set(resultLabel,
						labelToSubroutines.get(origLabel));
			}

			return resultLabel;
		}
	}

	/**
	 * Finds a {@code Subroutine} that is returned from by a {@code ret} in a
	 * given block.
	 * 
	 * @param label
	 *            A block that originally contained a {@code ret} instruction
	 * @return {@code null-ok;} found subroutine or {@code null} if none was
	 *         found
	 */
	private Subroutine subroutineFromRetBlock(int label) {
		for (int i = subroutines.length - 1; i >= 0; i--) {
			if (subroutines[i] != null) {
				Subroutine subroutine = subroutines[i];

				if (subroutine.retBlocks.get(label)) {
					return subroutine;
				}
			}
		}

		return null;
	}

	/**
	 * Removes all {@code move-return-address} instructions, returning a new
	 * {@code InsnList} if necessary. The {@code move-return-address} insns are
	 * dead code after subroutines have been inlined.
	 * 
	 * @param insns
	 *            {@code InsnList} that may contain {@code move-return-address}
	 *            insns
	 * @return {@code InsnList} with {@code move-return-address} removed
	 */
	private InsnList filterMoveReturnAddressInsns(InsnList insns) {
		int sz;
		int newSz = 0;

		// First see if we need to filter, and if so what the new size will be
		sz = insns.size();
		for (int i = 0; i < sz; i++) {
			if (insns.get(i).getOpcode() != Rops.MOVE_RETURN_ADDRESS) {
				newSz++;
			}
		}

		if (newSz == sz) {
			return insns;
		}

		// Make a new list without the MOVE_RETURN_ADDRESS insns
		InsnList newInsns = new InsnList(newSz);

		int newIndex = 0;
		for (int i = 0; i < sz; i++) {
			Insn insn = insns.get(i);
			if (insn.getOpcode() != Rops.MOVE_RETURN_ADDRESS) {
				newInsns.set(newIndex++, insn);
			}
		}

		newInsns.setImmutable();
		return newInsns;
	}

	/**
	 * Visits each non-subroutine block once in depth-first successor order.
	 * 
	 * @param firstLabel
	 *            label of start block
	 * @param v
	 *            callback interface
	 */
	private void forEachNonSubBlockDepthFirst(int firstLabel,
			BasicBlock.Visitor v) {
		forEachNonSubBlockDepthFirst0(labelToBlock(firstLabel), v, new BitSet(
				maxLabel));
	}

	/**
	 * Visits each block once in depth-first successor order, ignoring
	 * {@code jsr} targets. Worker for {@link #forEachNonSubBlockDepthFirst}.
	 * 
	 * @param next
	 *            next block to visit
	 * @param v
	 *            callback interface
	 * @param visited
	 *            set of blocks already visited
	 */
	private void forEachNonSubBlockDepthFirst0(BasicBlock next,
			BasicBlock.Visitor v, BitSet visited) {
		v.visitBlock(next);
		visited.set(next.getLabel());

		IntList successors = next.getSuccessors();
		int sz = successors.size();

		for (int i = 0; i < sz; i++) {
			int succ = successors.get(i);

			if (visited.get(succ)) {
				continue;
			}

			if (isSubroutineCaller(next) && i > 0) {
				// ignore jsr targets
				continue;
			}

			/*
			 * Ignore missing labels: they're successors of subroutines that
			 * never invoke a ret.
			 */
			int idx = labelToResultIndex(succ);
			if (idx >= 0) {
				forEachNonSubBlockDepthFirst0(result.get(idx), v, visited);
			}
		}
	}
}
